/*
** Made by texane <texane@gmail.com>
** 
** Started on  Sun Jan  6 20:36:50 2008 texane
** Last update Wed Jan  9 00:30:34 2008 texane
*/



#include <stdlib.h>
#include "bst.h"



/* node init
 */

static void bst_node_reset(bst_node_t* node)
{
  node->next = NULL;
  node->prev = NULL;
  node->parent = NULL;
  node->left = NULL;
  node->right = NULL;
}

void bst_node_init(bst_node_t* node)
{
  bst_node_reset(node);
}


void bst_node_release(bst_node_t* node)
{
  bst_node_reset(node);
}



/* tree init
 */

static void bst_tree_reset(bst_tree_t* tree)
{
  tree->root = NULL;
  tree->first = NULL;
}


void bst_tree_init(bst_tree_t* tree)
{
  bst_tree_reset(tree);
}


void bst_tree_release(bst_tree_t* tree,
		      void (*f)(bst_node_t*))
{
  bst_node_t* pos;
  bst_node_t* tmp;

  pos = tree->first;
  while (pos != NULL)
    {
      tmp = pos;
      pos = pos->next;
      f(tmp);
    }

  bst_tree_reset(tree);
}



/* tree iterator
 */

#if 0 /* dont use recursive traversal */

static void bst_tree_foreach_node_rec(bst_node_t* root,
				      void (*f)(void*, void*),
				      void* data)
{
  if (root == NULL)
    return ;

  bst_tree_foreach_node_rec(root->left, f, data);
  f(root->data, data);
  bst_tree_foreach_node_rec(root->right, f, data);
}


void bst_tree_foreach_node(bst_tree_t* tree,
			   void (*f)(void*, void*),
			   void* data)
{
  bst_tree_foreach_node_rec(tree->root, f, data);
}

#else

void bst_tree_foreach_node(bst_tree_t* tree,
			   void (*f)(void*, void*),
			   void* data)
{
  bst_node_t* pos;

  for (pos = tree->first; pos != NULL; pos = pos->next)
    f(pos->data, data);
}

#endif



/* node insertion
 */

void bst_tree_insert_node(bst_tree_t* tree,
			  bst_node_t* node,
			  int(*f)(void*, void*))
{
  bst_node_t* pos;
  bst_node_t* first;
  bst_node_t* parent;
  bst_node_t* next;
  bst_node_t* prev;
  bst_node_t** link;

  /* root special case
   */
  if (tree->root == NULL)
    {
      tree->first = node;
      tree->root = node;
      return ;
    }

  prev = NULL;
  first = node;
  link = NULL;
  pos = tree->root;
  first = node;

  /* find parent
   */
  while (pos != NULL)
    {
      parent = pos;

      if (f(pos->data, node->data) > 0)
	{
	  link = &pos->left;
	  pos = pos->left;
	}
      else
	{
	  prev = pos;
	  link = &pos->right;
	  first = tree->first;
	  pos = pos->right;
	}
    }

  /* update parent
   */
  node->parent = parent;
  *link = node;

  tree->first = first;

  /* update links
   */
  if (node == parent->right)
    {
      next = parent->next;
      parent->next = node;
    }
  else
    {
      next = parent;
    }

  if (next != NULL)
    {
      next->prev = node;
      node->next = next;
    }
  else
    {
      node->next = next;
    }

  if (prev != NULL)
    {
      node->prev = prev;
      prev->next = node;
    }
}



/* node removal
 */

static bst_node_t* get_leftmost_node(bst_node_t* root)
{
  bst_node_t* pos;

  pos = NULL;
  while (root != NULL)
    {
      pos = root;
      root = root->left;
    }

  return pos;
}


#if 0

static bst_node_t* get_rightmost_node(bst_node_t* root)
{
  bst_node_t* pos;

  pos = NULL;
  while (root != NULL)
    {
      pos = root;
      root = root->right;
    }

  return pos;
}


void bst_tree_remove_node(bst_tree_t* tree,
			  bst_node_t* node)
{
  bst_node_t* rightmost;
  bst_node_t* leftmost;

  if (node == tree->root)
    {
      /* case 1
       */
      if ((node->left != NULL) && (node->right != NULL))
	{
	  leftmost = get_leftmost_node(node->right);

	  leftmost->left = node->left;
	  tree->root = node->right;
	  node->left->parent = node->right;
	  node->right->parent = NULL;

	  get_rightmost_node(node->left)->next;
	  get_rightmost_node(node->right)->next;
	}
      /* case 2
       */
      else if (node->right != NULL)
	{
	  tree->root = node->right;
	  node->right->parent = NULL;

	  tree->first = get_leftmost_node(node->right);
	}
      /* case 3
       */
      else if (node->left != NULL)
	{
	  tree->root = node->left;
	  node->left->parent = NULL;

	  tree->first = get_leftmost_node(node->left);
	}
      /* case 4
       */
      else
	{
	  tree->first = NULL;
	  tree->root = NULL;
	}
    }
  else
    {
      if ((node->left != NULL) && (node->right != NULL))
	{
	  /* case 1
	   */
	  if (node == node->parent->left)
	    {
	      leftmost = get_leftmost_node(node->parent->right);
	      node->parent->left = node->left;
	      leftmost->left = node->right;

	      /* todos: recheck */

	      get_rightmost_node(node->left)->next = node->parent;
	      get_rightmost_node(node->right)->parent->right;

	      node->left->parent = node->parent;
	      node->right->parent = node->parent->right;

	      /* todos: recheck */
	    }
	  /* case 2
	   */
	  else
	    {
	      rightmost = get_rightmost_node(node->parent->left);
	      node->parent->right = node->right;
	      rightmost->right = node->left;

	      node->left->next = node->parent;
	      rightmost->next = node->left;

	      node->left->parent = node->parent->left;
	      node->right->parent = node->parent;
	    }
	}
      else if (node->left != NULL)
	{
	  /* case 3
	   */
	  if (node == node->parent->left)
	    {
	      node->parent->left = node->left;
	      node->left->next = node->parent;
	    }
	  /* case 4
	   */
	  else
	    {
	      node->parent->right = node->left;
	      node->parent->next = node;
	    }
	  node->left->parent = node->parent;
	}
      else if (node->right != NULL)
	{
	  /* case 5
	   */
	  if (node == node->parent->left)
	    {
	      node->parent->left = node->right;
	      node->right->next = node->parent;
	    }
	  /* case 6
	   */
	  else
	    {
	      node->parent->right = node->right;
	      node->parent->next = node;
	    }
	  node->right->parent = node->parent;
	}
      else
	{
	  /* case 7
	   */
	  if (node == node->parent->left)
	    {
	      node->parent->left = NULL;
	    }
	  /* case 8
	   */
	  else
	    {
	      node->parent->right = NULL;
	      node->parent->next = NULL;
	    }
	}
    }
}


#else


void bst_tree_remove_node(bst_tree_t* tree,
			  bst_node_t* node)
{
  bst_node_t** parent_link;
  bst_node_t* most;
  bst_node_t* child;

  /* list links update
   */
  if (tree->first == node)
    {
      if (node->right != NULL)
	tree->first = get_leftmost_node(node->right);
      else if (node->parent != NULL)
	tree->first = node->parent;
      else
	tree->first = NULL;
    }
  if (node->prev != NULL)
    node->prev->next = node->next;
  if (node->next != NULL)
    node->next->prev = node->prev;

  /* parent link
   */
  if (node->parent != NULL)
    {
      if (node == node->parent->left)
	parent_link = &node->parent->left;
      else
	parent_link = &node->parent->right;
    }
  else
    {
      parent_link = NULL;
    }

  /* 2 children node
   */
  if ((node->left != NULL) && (node->right != NULL))
    {
      most = get_leftmost_node(node->right);
      if (most != node->right)
	{
	  if (most->right != NULL)
	    {
	      most->parent->left = most->right;
	      most->right->parent = most->parent;
	    }
	  else
	    {
	      most->parent->left = NULL;
	    }
	  most->right = node->right;
	}
      most->left = node->left;

      child = most;

      /* common
       */
      most->parent = node->parent;
    }
  /* left child node
   */
  else if (node->left != NULL)
    {
      child = node->left;
    }
  /* right child node
   */
  else if (node->right != NULL)
    {
      child = node->right;
    }
  /* leaf node
   */
  else
    {
      child = NULL;
    }

  /* update parent_link
   */
  if (parent_link != NULL)
    *parent_link = child;
  else
    tree->root = child;

  /* update parent
   */
  if (child != NULL)
    child->parent = node->parent;
}


#endif



/* node lookup
 */

int bst_tree_find_node(bst_tree_t* tree,
		       int (*f)(void*, void*),
		       void* data,
		       bst_node_t** res)
{
  bst_node_t* pos;
  int val;

  *res = NULL;

  pos = tree->root;
  while (pos != NULL)
    {
      val = f(pos->data, data);
      if (!val)
	{
	  *res = pos;
	  return 0;
	}
      else if (val > 0)
	{
	  pos = pos->left;
	}
      else
	{
	  pos = pos->right;
	}
    }

  return -1;
}
